#include "stdafx.h"
#include <time.h>
#include <fstream>
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
#include <typeinfo>
#include <iterator>
#include <sstream>
#include <climits> // for CHAR_BIT
#include <iterator>

using namespace std;

class Profiler{
public:
	clock_t ticker;
	double elapse;
	void start(){
		ticker = clock();
	}
	void stop(){
		clock_t end = clock();
		elapse = (double)(end - ticker) / CLOCKS_PER_SEC;
		cout << "it took " << elapse << " seconds to execute" << endl;
	}
};


struct node{
public:
	unsigned int freq;
	char alpha;
	bool visited;
	node* left;
	node* right;
	node(char alpha, int freq){
		this->alpha = alpha;
		this->freq = freq;
		this->visited = false;
		this->left = NULL;
		this->right = NULL;
	}
	bool hasNeighboors(){
		return (this->left != nullptr || this->right != nullptr);
	}

	vector<node*> getNeighbors(){
		vector<node*> neighbors;
		if(this->left !=nullptr) neighbors.push_back(this->left);
		if(this->right !=nullptr) neighbors.push_back(this->right);
		return neighbors;
	}

};


/*stackoverflow.com/questions/1541560/stl-priority-queue-on-custom-class*/
struct DereferenceCompareNode : public std::binary_function<node*, node*, bool>
{
    bool operator()(const node* lhs, const node* rhs) const
    {
		return rhs->freq < lhs->freq; //min heap instead of <
    }
};


typedef vector<bool> code;
typedef unordered_map<char, code> codemap;
typedef  unordered_map<char,unsigned int> CharMapType;
typedef unsigned char uint8_t;

pair<char,unsigned int> mapPair;
CharMapType charMap;
priority_queue<node*,vector<node*>, DereferenceCompareNode> pq;
codemap codes;
/*stackoverflow.com/questions/3200954/what-is-char-bit*/
const int UniqueSymbols = 1 << CHAR_BIT;


node* buildHuffmanTree(const int (&frequencies)[UniqueSymbols]){
	for(int i=0; i < UniqueSymbols;i++){
		if(frequencies[i]!=0){
			node* n = new node(i,frequencies[i]);
			pq.push(n);
		}
	}

	string s = "";
	//construct the tree based on the book pg. 388 pseudocode line #3 to #9
	while(pq.size() >=2){
		node* x = pq.top();
		pq.pop();
		node* y = pq.top();
		pq.pop();
		node* z = new node(-1,x->freq + y->freq);
		z->left = x;
		z->right = y;
		pq.push(z);
	}
	return pq.top(); //return root, 
}


void traverseTree(node* n, code& prefix, codemap& outCodes){
	bool isLeaf = !n->hasNeighboors();

	if(isLeaf){
		outCodes[n->alpha] = prefix;
	}else{
        code leftPrefix = prefix;
        leftPrefix.push_back(false);
        traverseTree(n->left, leftPrefix, outCodes);
        code rightPrefix = prefix;
        rightPrefix.push_back(true);
        traverseTree(n->right, rightPrefix, outCodes);
	}

}

//bro draper format specs
string replaceChar(char c){
	switch(c){
	case 32: 
		return "space";break;
	case 13:
		return "return";break;
	case 10:
		return "newline";break;
	case 9:
		return "tab";break;
	default:
		stringstream ss;
		string s;
		ss << c;
		ss >> s;
		return s;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	//what if the user forgot to include a command line parameter?
	if (argc < 2) {
		cout << "missing command-line parameter" << endl;
		exit(1);
	}

	//attempt to open  file
	ifstream infile;
	infile.open(argv[1]);
	if (!infile) {
		cout << "Cannot find input file." << endl;
		exit(1);
	}

	/*stackoverflow.com/questions/6291458/how-to-convert-tchar-array-to-stdstring*/
	#ifndef UNICODE  
	  typedef std::string String; 
	#else
	  typedef std::wstring String; 
	#endif
	
	/*stackoverflow.com/questions/4804298/how-to-convert-wstring-into-string*/
	String f = argv[1];
	string iFilename( f.begin(), f.end() );

	Profiler* prof = new Profiler();
	prof->start();

	cout << "reading characters" << endl; 
	//map of character frequencies

	string inputStr;
	infile.seekg(0, std::ios::end);   
	inputStr.reserve(infile.tellg());
	infile.seekg(0, std::ios::beg);

	inputStr.assign((std::istreambuf_iterator<char>(infile)),
				std::istreambuf_iterator<char>());

	int frequencies[UniqueSymbols] = {0};
	const char* pointer = inputStr.c_str();
    while (*pointer != '\0'){
        ++frequencies[*pointer++];
	}
	prof->stop();
	cout << "reading characters done!" << endl; 

	//construct the huffman tree
	cout << "building tree" << endl;
	node* root = buildHuffmanTree(frequencies);

	cout << "building tree done!" << endl;

	traverseTree(root,code(),codes);
	cout << "getting codes, traversing the tree" << endl;

	cout << "getting codes, traversing the tree done!" << endl;
	delete root;

	ofstream out;

	iFilename = iFilename.substr(0,iFilename.length()-3); //strip the extension of the file name;
	iFilename+="zip301"; //append zip301 extension;

	out.open(iFilename); 
    if( !out.is_open()) 
		out.open(iFilename, ios_base::in | ios_base::out | ios_base::trunc);

	string allbits;
	int totalbits=0;
	unordered_map<char,string> strcodes;
    for (codemap::const_iterator it = codes.begin(); it != codes.end(); ++it)
    {
		ostringstream ss;
		copy(it->second.begin(), it->second.end(),ostream_iterator<bool>(ss));
		out << ss.str();
		int freq = frequencies[it->first];
		//compute bit length
		int bitlength = ss.str().length();
		totalbits+=freq*bitlength;
		out << " " << replaceChar(it->first) << endl;	
		strcodes[it->first] = ss.str();
    }
	out << "*****" << endl; 
	out << totalbits <<endl;


	cout << "encoding characters" << endl;
	unsigned int bitlength = inputStr.length();
	for(int i = 0; i < inputStr.length();i++){
		allbits+=strcodes[inputStr[i]];
	}

	cout << "encoding characters done!" << endl;
	//pad the bits so its a multiple of 8 bits (byte)
	for(unsigned int i = 0; i < (allbits.length() % 8);i++){
		allbits+="0";
	}

	bitlength = allbits.length();

	string tmp;

	cout << "packing bits per byte" << endl;
	for(int i=0; i < bitlength;i++){
		tmp+=allbits[i];
		if((i+1) % 8 == 0){
			/*stackoverflow.com/questions/15587781/c-storing-a-string-containing-binary-into-a-text-file*/
			uint8_t byte = strtoul(tmp.c_str(), NULL, 2);
			out << byte;
			tmp="";
		}
	}

	cout << "packing bits per byte done!" << endl;
	out.close();
	
	cout << "write to file complete!" << endl;
	prof->stop();

}

